poj 2486 Apple Tree(트리 백팩)

제목: 나무 한 그루를 주면 나무의 각 노드마다 대응하는 수량의 사과가 있다. 한 사람은 어느 지점에서 출발해서든 k보 이내에서 가장 많은 사과를 얻을 수 있는 방법을 물어볼 수 있다. 문제 풀이: 분석에 의하면 이 문제는 나무를 걷는 경로에 대해 왕복과 왕복하지 않는 상황이 있고 한 길을 여러 번 반복할 수 있다는 것을 알아차렸다. 그러면 이러한 상태 dp[root][j][st]뿌리 노드 ...

동적 기획동적 계획 - 트리 dp